#ifndef _QUICK_SORT_
#define _QUICK_SORT_

#include<vector>
#include<algorithm>
#include<cstdlib>

template <typename T>
void bubble_sort(std::vector<T> & data,int begin,int end){
    for(int i=begin;i<=end;i++){
        int x=i;
        for(int j=i;j<=end;j++){
            if(data[j]<data[x]) x=j;
        }
        std::swap(data[x],data[i]);
    }
}

template <typename T>
inline int choose(std::vector<T> & data,int begin, int end){
    int j;
    for(j=end;j>begin;j--) if(data[begin]!=data[j]) break;
    return j;
}


template <typename T>
void quick_sort0(std::vector<T> & data, int begin ,int end){
    if(begin>=end) return;
    else if(end-begin<=10){
        bubble_sort(data,begin,end);
        return;
    }
    int i=begin, j=end;
    int index=rand()%(j-i+1)+i;
    T cmp=data[index];
    while(i<j){
        while(i<j&&data[j]>cmp) j--;
        while(i<j&&data[i]<=cmp) i++;
        if(i<j) std::swap(data[i],data[j]);
    }
    if(j==end) std::swap(data[index],data[i]);
    quick_sort0(data,begin,i);
    quick_sort0(data,i+1,end);
}

template <typename T>
void quick_sort(std::vector<T> & data, int begin ,int end){
    if(begin>=end) return;
    else if(end-begin<=10){
        bubble_sort(data,begin,end);
        return;
    }
    int i=begin, j=end;
    int index=(i+j)/2;
    T cmp=data[index];
    while(i<j){
        while(i<j&&data[j]>cmp) j--;
        while(i<j&&data[i]<=cmp) i++;
        if(i<j) std::swap(data[i],data[j]);
    }
    if(j==end) std::swap(data[index],data[i]);
    quick_sort(data,begin,i);
    quick_sort(data,i+1,end);
}

template <typename T>
void quick_sort1(std::vector<T> & data, int begin ,int end){
    if(begin>=end) return;
    else if(end-begin<=10){
        bubble_sort(data,begin,end);
        return;
    }
    int i=begin, j=end, index=choose(data,begin,end);
    if(index==begin) return;
    T cmp=data[begin]<data[index]?data[begin]:data[index];
    while(i<j){
        while(i<j&&data[j]>cmp) j--;
        while(i<j&&data[i]<=cmp) i++;
        if(i<j) std::swap(data[i],data[j]);
    }
    quick_sort1(data,begin,i);
    quick_sort1(data,i+1,end);
}

template <typename T>
void sort_MoT(std::vector<T> & A){
    quick_sort(A,0,A.size()-1);
}

template <typename T>
void sort_random(std::vector<T> & A){
    quick_sort0(A,0,A.size()-1);
}

template <typename T>
void sort_average(std::vector<T> & A){
    quick_sort1(A,0,A.size()-1);
}
#endif